// /**
//  * https://leetcode.cn/problems/coin-change/
//  * @param {number[]} coins
//  * @param {number} amount
//  * @return {number}
//  */
// var coinChange = function(coins, amount) {
//     if(coins.length<1){
//         return -1;
//     }
//     console.log(coins,amount)
//     let sortCoins=coins.sort((a,b)=>b-a)
//     let space=amount;
//     let total=0;
//     console.log('sortCoins',sortCoins)
//     for (const coin of sortCoins) {
//         console.log('循环',space,coin)
//         if(space>0){
//             let count=Math.floor(space/coin);
//             total+=count;
//             space-=coin*count
//             console.log('有余',space,coin,count)
//         }else{
//             break;
//         }
        
//     }
//     console.log('total',total,space)

//     return space>0?coinChange(coins.slice(1),amount):total;

// };


/**
 * https://leetcode.cn/problems/coin-change/
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    coins=coins.filter(x=>x<=amount)
    if(coins.length<1){
        return -1;
    }
    console.log(coins,amount)
    let sortCoins=coins;
    let space=amount;
    let total=0;
    let res={}
    console.log('sortCoins',sortCoins)
    for (const coin of sortCoins) {
        console.log('循环',space,coin)
        if(space>0){
            let count=Math.floor(space/coin);
            total+=count;
            space-=coin*count
            console.log('有余',space,coin,count)
            res[coin]=count;
            res['total']=total;
            res['remain']=space;
        }else{
            break;
        }
        
    }
    console.log('res',res)

    return space>0?coinChange(coins.slice(1),amount):total;

};

coins = [1, 2, 5], amount = 11

// console.log('res',coinChange([1,2,4],3));
// [186,419,83,408]
// 6249
// console.log('res',coinChange([3],2));
 //console.log('res',coinChange([186,419,83,408],6249));

 
 /**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange4 = function (coins, amount) {
    if (amount === 0) return 0;
    let dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    let cache=[];
    for (let i = 1; i <= amount; i++) {
        cache[i]={}
      for (let j = 0; j < coins.length; j++) {
        
        cache[i][coins[j]]=0;
        if (coins[j] <= i) {
            cache[i][coins[j]]+=1;
          dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
          
        }
      }
    }
    console.log(cache)
    console.log(dp)
    return dp[amount] === Infinity ? -1 : dp[amount];
  };
  console.log('res',coinChange4([1,3,5],11));
//   console.log('res',coinChange4([186,419,83,408],6249));